/**
 * The rand7() API is already defined in the parent class SolBase.
 * public int rand7();
 *
 * @return a random integer in the range 1 to 7
 */
package vip.zhenzicheng.algorithm.leetcode.random;

/**
 * <a href="https://leetcode.cn/problems/implement-rand10-using-rand7/">用 Rand7() 实现 Rand10() [中等]</a>
 *
 * @author zhenzicheng
 * @date 2022-06-14 15:32
 */
public class ImplementRand10UsingRand7_470 extends SolBase {

  int x = 0;

  public int rand10() {
    return rand9() + 1; // [1,10]等概率
  }

  public int rand9() {
    do {
      x = rand15();
    } while (x > 9);
    return x;
  }

  /*改造成 0000-1111，即[0,15]等概率*/
  public int rand15() {
    // [0,15]等概率
    x = (rand1() << 3) + (rand1() << 2) + (rand1() << 1) + rand1(); // [0,15] 等概率
    //return x > 9 ? rand9() : x; // 改造成[0,9]等概率
    return x;
  }

  /*首先将rand7改成[0,1]上等概率发生的函数*/
  public int rand1() {
    do {
      x = rand7();
    } while (x == 4);
    return x < 4 ? 0 : 1;
  }
}

/*不需要提交，leetcode提供一个黑盒方法*/
class SolBase {
  final int rand7() {
    return (int) (Math.random() * 7) + 1;
  }
}
